package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/3/20 9:42 AM
 *
 * https://leetcode-cn.com/problems/maximum-binary-tree/
 */
public class _654_最大二叉树 {


    public TreeNode constructMaximumBinaryTree(int[] nums) {

        if (nums == null || nums.length == 0) {

            return null;
        }

        return findRoot(nums,0,nums.length);
    }

    private TreeNode findRoot(int[] nums, int start, int end) {

        int maxIndex = start;

        for (int i = start + 1; i < end; i++) {

            if (nums[maxIndex] < nums[i]) {

                maxIndex = i;
            }
        }

        TreeNode root = new TreeNode(nums[maxIndex]);

        if (maxIndex - start > 0) {

            root.left = findRoot(nums,start,maxIndex);
        }else {

            root.left = null;
        }

        if (end > maxIndex + 1) {

            root.right = findRoot(nums,maxIndex + 1,end);
        }else {

            root.right = null;
        }

        return root;
    }



}
